package com.hw.collection;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class HeapImpl<T> implements Heap<T>{
	private List<T> heap;
	private Comparator<T> comparator=null;
	
	//getters and setters
	
	public List<T> getHeap() {
		return heap;
	}
	public void setHeap(List<T> heap) {
		this.heap = heap;
	}
	public Comparator<T> getComparator() {
		return comparator;
	}
	public void setComparator(Comparator<T> comparator) {
		this.comparator = comparator;
	}
	
	/************************************END getters and setters**********/
	//constructors
	public HeapImpl(int size, Comparator<T> com){
		heap=new ArrayList<T>(size);
		comparator=com;
	}
	public HeapImpl(){
		heap=new ArrayList<T>();
	}
	public HeapImpl(int size){
		heap=new ArrayList<T>(size);
	}
	/***************************** END Constructors ***********************/
	@SuppressWarnings("unchecked")
	public int compareObjects(T e1, T e2){
		if(comparator!=null){
			return comparator.compare(e1, e2);
		}
		//using comparable
		
		Comparable<? super T> key = (Comparable<? super T>) e1;
		return key.compareTo((T) e2);
	}
	private void heapifyDown(int i){
		int l=2*i+1;
		int r=2*i+2;
		if(l>=heap.size())
			return;
		else if(r>=heap.size() && compareObjects(heap.get(l),heap.get(i))>0 )
			swap(i,l);
		else if(compareObjects(heap.get(l),heap.get(i))>0 &&compareObjects(heap.get(l),heap.get(r))>0){
			swap(i,l);
			heapifyDown(l);
		}
		if(r>=heap.size())
			return;
		else if(compareObjects(heap.get(r),heap.get(i))>0 && compareObjects(heap.get(r),heap.get(l))>0){
			swap(i,r);
			heapifyDown(r);
		}
		
	}
	/*
	 * SWAP ELEMENTS IN HEAP
	 */
	private void swap(int i1,int i2){
		T el=heap.get(i1);
		heap.set(i1, heap.get(i2));
		heap.set(i2, el);
	}
	
	/*
	 * HEAPIFY UPWARDS FROM AN INDEX
	 */
	private void heapifyUp(int i){
		if(i==0)
			return;
		int parent=(i-1)/2;
		if(compareObjects(heap.get(i),heap.get(parent))>0){
			swap(i,parent);
			heapifyUp(parent);
		}
	}
	
	/*
	 * SEARCH FOR AN ELEMENT
	 */
	private int search(T element){
		return search(element,0);
	}
	private int search(T element, int i){
		if(element.equals(heap.get(i)))
			return i;
		if(compareObjects(element,heap.get(i))>0 || i>=heap.size())
			return -1;
		int l=2*i+1;
		int r=l+1;
		int li = -1,ri = -1;
		if(compareObjects(heap.get(l),element)>=0)
			li=search(element,l);
		if(compareObjects(heap.get(r),element)>=0)
			ri=search(element,r);
		return (li>=0)?li:ri;
	}
	/*
	 * ADD AN ELEMENT
	 */
	public void add(T element){
		heap.add(element);
		heapifyUp(heap.size()-1);
	}
	
	/*
	 * ADD AN ARRAY OF ELEMENTS : HEAPIFY DOWNWARDS
	 * COMPLEXITY - 0(N)
	 */
	public void addAll(T[] elements){
		int curSize=heap.size();
		int newSize=curSize+elements.length;
		for(int i=0;i<elements.length;i++)
			heap.add(elements[i]);
		newSize--;
		for(int i=newSize/2;i>=0;i--){
			heapifyDown(i);
		}
	}
	
	public void addAllHeapifyUp(T[] elements){
		int curSize=heap.size();
		int newSize=curSize+elements.length;
		for(int i=0;i<elements.length;i++)
			heap.add(elements[i]);
		for(int i=0;i<newSize;i++){
			heapifyUp(i);
		}
	}
	/*
	 * DELETE ELEMENT AT 0, INDEX I OR GIVEN AN OBJECT T
	 */
	public  T delete(){
		int size=heap.size();
		swap(0,size-1);
		T el=heap.remove(size-1);
		heapifyDown(0);
		return el;
		
	}
	public T delete(int i){
		i--;//get 0 based index
		int size=heap.size();
		swap(i,size-1);
		T el=heap.remove(size-1);
		if(compareObjects(heap.get(i),heap.get(2*i))>0 && compareObjects(heap.get(i),heap.get(2*i+1))>0)
			heapifyUp(i);
		else
			heapifyDown(i);
		return el;
	}
	public T delete(T element){
		int i=search(element);
		if(i<0)
			return null;
		return delete(i);
		
	}
	
	/*
	 * CHECK IF ELEMENT PRESENT
	 */
	public boolean isPresent(T element){
		return search(element)>=0;
	}
	
	public T peek(){
		if(heap.isEmpty())
			return null;
		else
			return heap.get(0);
		
	}
	
	public void printHeap(){
		int skipval=2;
		for(int i=0;i<heap.size();i++){
			if(i==skipval-1){
				System.out.println();
				skipval<<=1;
			}
			System.out.print(heap.get(i).toString()+ " ");
		}
		System.out.println();
	}
}


